/**
 * 47. 全排列 II
 *
 * 【中等】
 *
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 * 示例 1：
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * 	[1,2,1],
 *  [2,1,1]]
 *
 * 示例 2：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */

function permuteUnique(nums: number[]): number[][] {
	const len = nums.length
	const ans: number[][] = []
	const visited = {}
	const path: number[] = []

	// 排序后，相同的数字就相邻了，便于去重
	nums.sort((a, b) => a - b)

	const dfs = (index) => {
		if (path.length === len) {
			ans.push(path.slice())
			return
		}

		for (let i = 0; i < len; i++) {
			// 两数相等，并且元素下标用过
			if (nums[i - 1] === nums[i] && i >= 1 && !visited[i - 1]) continue
			if (visited[i]) continue

			path.push(nums[i])
			// 与 全排列  不同的是，要纪录下标是不是用过，而不是元素本身
			visited[i] = true

			dfs(index + 1)

			path.pop()
			visited[i] = false
		}
	}

	dfs(0)

	return ans
}
